1. Field of the Invention
The present invention relates generally to packet-based communication systems and more particularly to packet-based data routing.
2. Description of the Related Art
Data is a generic term that denotes facts, numbers, letters and/or symbols that convey information. Data typically includes digital data signals (signal information in digital form), voice signals (signals in a frequency band that represent voice) and video signals (signals in a frequency band that represent images).
The type of data traffic generally determines appropriate routing techniques when that data is carried over a communications system. Voice data, for example, requires a dedicated communication path to facilitate real-time communication. In contrast, digital data signals tend to be bursty in nature, need not be communicated in real time and can therefore share network resources with other bursty users. Some types of data have an urgent delivery schedule while others can be sent when convenient.
Data signals are therefore often routed through communication systems in accordance with different routing methods. A first method is connection-oriented routing in which a communications path between a signal source and a signal destination is fixed for the duration of the message. Because the path is fixed, the data arrives at the receiver in the order it was transmitted. A connection-oriented service typically uses error control coding to provide data protection in case the network connection becomes noisy. If the message is degraded (e.g., by noise), it must be retransmitted from the beginning.
A second method is connectionless routing which relie""s on packet-based transmissions in which the message is divided into data packets which are separately routed through the system. Because these packets do not necessarily travel over the same route nor arrive in the order of transmission, they carry overhead information (e.g., source address, destination address, routing information and packet-order information) that maintains message integrity. Because of the overhead information, connectionless routing typically avoids the need to retransmit an entire message.
Noisy transmission links, however, introduce errors into the packet-based data. When data packets do not arrive error free at the receiver, they must be retransmitted and this action necessarily degrades the communication system""s data throughput. The noise can be quantified by its induced bit error rate and, generally, the higher the bit error rate, the greater the number of packets which must be retransmitted and the lower the system throughput.
Various methods have been proposed to improve throughput by modifying the transmission of packets. In U.S. Pat. No. 5,818,852, for example, a frame""s data is divided into smaller portions (termed xe2x80x9csubframesxe2x80x9d) which each have a respective error code. In addition, a frame header carries routing and identification information and an error code is also generated for the header.
At the receiver, error-free subframes are stored but an acknowledgment is sent to the transmitter only if all subframes are error free. In the absence of an acknowledgement, the transmitter continues to retransmit the entire frame until all of its subframes have been received error free.
Another proposed method for improving communication throughput is found in U.S. Pat. No. 5,629,948. In addition to data, each transmission frame in this Patent has a control section that includes data for directing transmission and retransmission and for frame identification. Similar to U.S. Pat. No. 5,818,852, the data in each frame is formed with a plurality of data sections but, in contrast, each carries a respective error-correction code. Upon frame reception, the error-free data sections are saved and an acknowledgement sent back to the transmitter.
In further contrast to U.S. Pat. No. 5,818,852, the data sections that have errors are also saved and a retransmission request is sent to the transmitter for each of these error-containing data sections. In response, the transmitter produces an error correction code for each error-containing data section. When the transmitter has received M retransmission requests, it forms a frame with the respective error correction codes and transmits this frame. In an exemplary process, N=M=3.
With a first one of the error-correction codes, the receiver carries out an error-correction operation with each stored error-containing data section because the order of the error-correction codes may differ from the order of the stored error-containing data sections. When an error-containing data section is corrected to be error free, an acknowledgment is sent to the transmitter and the process repeated for each of the other error-correction codes.
In a low-noise transmission link, these proposed packet-transmission methods will typically improve throughput because each subframe (or data section) does not have to individually carry the overhead (e.g., routing and identification information) that is supplied by its frame. However, U.S. Pat. No. 5,629,948 carries additional overhead of individual packet error codes and requires time-consuming storing of error-free subframes in noisy conditions even though entire frames are retransmitted. U.S. Pat. No. 5,818,852 also carries additional overhead of individual packet error codes and adds a complex, time-consuming error-correction process.
The present invention is directed to packet-based communication methods and systems that have improved data throughput and that can effectively modify themselves to respond to different error-rate conditions.
In one method embodiment, data frames are initially formed to each have N data packets and a frame error code. Data frames are then transmitted and checked. In response to the check, data packets of error-free data frames are routed through the system and data frames that are in error are retransmitted. The checking, processing and retransmitting steps are repeated until all data packets are routed through the communication system.
In another method embodiment, data frames are again initially formed to each have N data packets and a frame error code. Data frames are then transmitted and checked and in response to the check, data packets of error-free data frames are routed through the system. In contrast, however, data packets of each data frame found to be in error in the checking step are inserted into a data frame of the forming step. Transmitting, checking, routing and inserting steps are then repeated until all data packets are routed.
In a feedback feature of the invention, a system error rate is determined and, in response, N is periodically updated to a value that realizes the best data throughput under the current noise condition of the transmission link.
In the invention""s methods, frame overhead is reduced by carrying only a frame error code and feedback is provided to respond to changing error rate conditions by adjusting N to a value that realizes the best data throughput for the changed conditions. A choice of retransmission processes (i.e., with or without insertion into a frame of the forming step) provides further process flexibility for increasing throughput in different bit error rate conditions.
The teachings of the invention can be practiced with communication systems that include data sources and sinks, data-interconnection modules, transceivers, transmission links and processors that are programmed to direct the systems along the methods of the invention.
The novel features of the invention are set forth with particularity in the appended claims. The invention will be best understood from the following description when read in conjunction with the accompanying drawings.